/**
 * @Author Fizz Pu
 * @Date 2020/10/25 下午7:45
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */

/**
 * 给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
 *
 * 你可以对一个单词进行如下三种操作：
 *
 * 插入一个字符
 * 删除一个字符
 * 替换一个字符
 * 输入：word1 = "horse", word2 = "ros"
 * 输出：3
 * 解释：
 * horse -> rorse (将 'h' 替换为 'r')
 * rorse -> rose (删除 'r')
 * rose -> ros (删除 'e')
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/edit-distance
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/edit-distance
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

// 字符串的dp问题
// 都是最长公共子序列的变体
// jiu  fji
// 字符相等  字符不相等 三种选择

public class Lee72 {
    public int minDistance(String word1, String word2) {
        if(word1 == null || word2 == null)throw new IllegalArgumentException();

        int word1Len = word1.length(), word2Len = word2.length();
        int[][] dp = new int[word1Len+1][word2Len+1];

        // 初始化
        for(int i = 0 ; i <= word2Len; ++i)dp[0][i] = i;

        for(int j = 0; j <= word1Len; ++j)dp[j][0] = j;

        for(int row = 1; row <= word1Len; ++row){
            for(int col = 1; col <= word2Len; ++col){
                if(word1.charAt(row-1) == word2.charAt(col-1)){
                    dp[row][col] = dp[row-1][col-1];
                } else{
                    // dp[row][col-1] dp[row-1][col-1] dp[row-1][col]
                    dp[row][col] = Math.min(dp[row][col-1]+1,Math.min(dp[row-1][col]+1, dp[row-1][col-1]+1));
                }
            }
        }
        return dp[word1Len][word2Len];
    }

    public static void main(String[] args) {
        Lee72 lee72 = new Lee72();
        System.out.println(lee72.minDistance("horse", "ros"));
        System.out.println(lee72.minDistance("", "rose"));
        System.out.println(lee72.minDistance("", ""));
    }
}
